///////////////////////////////////////////////////
/// tototoy Code
/// $Id: bytetree.cc 26 2009-09-25 13:26:15Z tonyjobmails $
/// $Date: 2009-09-25 21:26:15 +0800 (五, 2009-09-25) $
/// $Author: tonyjobmails $
/// $Revision: 26 $
/// E-mail: tonyjobmails@gmail.com
/// filename: bytetree.cc
/// function: 动态256叉树的实现
///////////////////////////////////////////////////

#include "bytetree.h"

using namespace tototoy;

///////////////////////////////////////////
/// @brief 删除结点
template<typename _T>
void _node_byte<_T>::_delete(_node_byte<_T>* &op_data)
{
	if(op_data)
	{
#ifdef _TONY_DEBUG
		std::cout << "调用重载bytetree结点的delete:" << op_data->data << ", 孩子结点个数:" << op_data->child_num << std::endl;
#endif
		_uint_16 idx = 0;
		idx = 0;
		/// 释放孩子结点
		while(idx < op_data->child_num)
		{
			if(op_data->child_ptr && op_data->child_ptr[idx])
			{
				delete op_data->child_ptr[idx];
				op_data->child_ptr[idx] = NULL;
			}
			++idx;
		}
		/// 释放孩子指针
		if(op_data->child_ptr)
		{
			delete[] op_data->child_ptr;
			op_data->child_ptr = NULL;
		}
		/// 释放链
		if(op_data->linker)
		{
			op_data->linker->delete_list();
		}
		delete op_data;
		op_data = NULL;
	}
}
///////////////////////////////////////////


///////////////////////////////////////////
/// @brief 构造函数
byte_tree::byte_tree()
{
	this->max_deep = 0;
	this->root = new _node_type;
}
///////////////////////////////////////////

///////////////////////////////////////////
/// @brief 析构函数
byte_tree::~byte_tree()
{
	this->delete_tree();
	this->max_deep = 0;
}
///////////////////////////////////////////

///////////////////////////////////////////
/// @brief 递归地删除整个树
/// @return 成功与否
bool byte_tree::delete_tree()
{
	action_free_tree_pointer action;
	byte_tree::traver_tree(this->root, &action);
	return true;
}
///////////////////////////////////////////

///////////////////////////////////////////
/// @brief 查找删除一条链
/// @param chain：要删除的链
/// @return：成功与否
bool byte_tree::delete_chain(_link_list_type const &chain)
{
	_node_type *node = this->search_chain(chain);
	if(node)
		return byte_tree::delete_chain(this, node);
	return false;
}
///////////////////////////////////////////

///////////////////////////////////////////
/// @brief 查找删除结点所在的一条链
/// @param chain：要删除的链
/// @return：成功与否
bool byte_tree::delete_chain(byte_tree *tree, _node_type *node)
{
	if(node && node->child_ptr == NULL)
	{
		action_clear_node_linker_node action;
		op::_condition<_node_type *> cond_in;
		op::condition<_node_type *> cond;
		cond.set_logic(op::_LOGIC_OR);		/// 逻辑为或

		_node_type *del = node;
		_node_type *parent = node->parent_ptr;
		while(del && del != tree->root)
		{
			/// 加入条件列表
			cond_in.cond_data = del;
			cond_in.equal = true;
			cond.add_condition(cond_in);
			/// 如果没有孩子, 则删除这个结点
			_uint_16 idx = 0;
			/// 清除父结点的保存的此结点指针
			if(parent)
			{
				bool search = false;
				while(idx < parent->child_num)
				{
					/// 先找到要删除的孩子结点
					if(!search)
					{
						/// 清除
						if(parent->child_ptr && parent->child_ptr[idx]
								&& parent->child_ptr[idx] == del)
						{
							parent->child_ptr[idx] = NULL;
							search = true;
						}
					}
					else
					{
						/// 清除了结点，则把所以后面的结点往前移一个
						parent->child_ptr[idx - 1] = parent->child_ptr[idx];
					}
					++idx;
				}
				/// 找到结点, 表示已删除
				if(search && parent->child_ptr)
				{
					if(!_de_new<_node_type *>(parent->child_ptr, parent->child_num, 1))
					{
#ifdef _TONY_DEBUG
						std::cout << "_de_new出错, 此错误会导致数据结构混乱" << std::endl;
#endif
						return false;
					}
					parent->child_num--;
				}
			}
			_node_byte<_character_type>::_delete(del);
			if(parent)
			{
				del = parent;
				parent = del->parent_ptr;
			}
			else break;
		}
		
		/// 遍历整个树，删除结点指向linker链表中为此次删除链中结点的元素
		byte_tree::traver_tree(tree->root, &action);

		return true;
	}
	return false;
}
///////////////////////////////////////////

///////////////////////////////////////////
/// @brief 插入一条链(理解为一个talking)
/// @param chain：要插入的链
/// @param lear_node：这条链在本树中的叶子结点(最后一个结点)
/// @return 成功与否
bool byte_tree::insert_chain(_link_list_type const &chain, _node_type* &leaf_node)
{
	/// 如果要结点为空，分配空间
	if(this->root == NULL)
	{
		this->root = new _node_type;
		if(!this->root)
		{
#ifdef _TONY_DEBUG
			std::cout << "分配内存失败(FUNCTION:" << __FUNCTION__
				<< ", LINE: " << __LINE__ << ")"<< std::endl;
#endif
			return false;
		}
	}
	if(this->root)
	{
		bool direct_insert = false;	/// 一旦在树中找不到元素，那么后的面元素必将是要分配孩子结点的
		_node_type *node = this->root;
		_character_type elem;
		_uint_16 idx = 1;
		while(chain.get_pos_elem(idx++, elem))
		{
			if(node && node->child_ptr)
			{
				bool findout = false;
				_uint_16 pos = 0;
				while(!direct_insert && node->child_ptr && pos < node->child_num)
				{
					/// 找到相同的元素，则下一次从此孩子结点开始
					if(node->child_ptr[pos] && elem == node->child_ptr[pos]->data)
					{
						node = node->child_ptr[pos];
						findout = true;
						break;
					}
					++pos;
				}
				/// 如果有找到相同元素，开始下一个元素的循环
				if(findout)
					continue;
				/// 走到此处，说明孩子结点没有这个元素，要追加分配空间，并把这个元素加入
				direct_insert = true;
				_node_type *insert = new _node_type;
				if(insert)
				{
					insert->data = elem;
					if(_in_new<_node_type *>(node->child_ptr, node->child_num, node->child_num + 1)
						&& node->child_ptr)
					{
						insert->parent_ptr = node;
						node->child_ptr[node->child_num] = insert;
						node->child_num++;
						node = insert;
					}
					else
					{
#ifdef _TONY_DEBUG
						std::cout << "分配内存失败(FUNCTION:)" << __FUNCTION__
							<< ", LINE: " << __LINE__ << std::endl;
#endif
						delete insert;
						return false;			/// 分配内存失败
					}
				}
				else
				{
#ifdef _TONY_DEBUG
					std::cout << "分配内存失败(FUNCTION:)" << __FUNCTION__
						<< ", LINE: " << __LINE__ << std::endl;
#endif
					return false;				/// 分配内存失败
				}
			}
			/// 没有孩子结点的情况
			else
			{
				if(node && !node->child_ptr)
				{
					direct_insert = true;
					node->child_ptr = new _node_type*[1];
					if(node->child_ptr)
					{
						node->child_ptr[0] = new _node_type;
						if(node->child_ptr[0])
						{
							node->child_num++;
							node->child_ptr[0]->parent_ptr = node;
							node->child_ptr[0]->data = elem;
							node = node->child_ptr[0];
						}
						else
						{
							delete[] node->child_ptr;
#ifdef _TONY_DEBUG
							std::cout << "分配内存失败(FUNCTION:)" << __FUNCTION__
								<< ", LINE: " << __LINE__ << std::endl;
#endif
							return false;
						}

					}
					else
					{
#ifdef _TONY_DEBUG
						std::cout << "分配内存失败(FUNCTION:)" << __FUNCTION__
							<< ", LINE: " << __LINE__ << std::endl;
#endif
						return false;
					}
				}
			}
		}
		leaf_node = node;						/// 最后一个结点
		return true;
	}
	else
	{
#ifdef _TONY_DEBUG
		std::cout << "分配内存失败(FUNCTION:)" << __FUNCTION__
			<< ", LINE: " << __LINE__ << std::endl;
#endif
		return false;			/// 分配内存失败
	}
}
///////////////////////////////////////////

///////////////////////////////////////////
/// @brief 插入一条回型链(理解为一个talk+answer)
/// @param chain：要插入的链
/// @param rechain：要插入的反链
/// @return 成功与否
bool byte_tree::insert_circle_chain(_link_list_type const &chain, _link_list_type const &rechain)
{
	_node_type *chain_node = NULL;
	_node_type *rechain_node = NULL;
	if(this->insert_chain(chain, chain_node) && this->insert_chain(rechain, rechain_node) && chain_node && rechain_node)
	{
		if(!chain_node->linker)
			chain_node->linker = new link_list<_node_type *>;
		if(chain_node->linker)
		{
			///////////////////////////
			/// 这个要改，不能插入到最后，按这权值的顺序插入(且不能重复)
			chain_node->linker->insert_by_order(rechain_node);
#ifdef _TONY_DEBUG
			std::cout << "成功插入回型链" << std::endl;
#endif
			///////////////////////////
			return true;
		}
	}
	return false;
}
///////////////////////////////////////////

///////////////////////////////////////////
/// @brief 插入一条反链(理解为一个talk的answer)
/// @param chain：在这个链后插入反链
/// @param rechain：要插入的反链
/// @return 成功与否
bool byte_tree::insert_rechain(_link_list_type const &chain, _link_list_type const &rechain)
{
	_node_type *node = this->search_chain(chain);
	_node_type *rechain_node = NULL;
	if(node && this->insert_chain(rechain, rechain_node) && rechain_node)
	{
		if(!node->linker)
			node->linker = new link_list<_node_type *>;
		if(node->linker)
		{
			///////////////////////////
			/// 这个要改，不能插入到最后，按这权值的顺序插入(且不能重复)
			node->linker->insert_by_order(rechain_node);
			//////////////////////////
			return true;
		}
	}
	return false;
}
///////////////////////////////////////////

///////////////////////////////////////////
/// @brief 查找一条链(返回最后一个结点指针)
/// @param chain：要查找的链
/// @return 成功返回一个结点，失败返回root结点
_node_byte<_character_type>* byte_tree::search_chain(_link_list_type const &chain)
{
	_node_type *p_result = NULL;
	if(chain.get_length() > 0)
	{
		p_result = this->root;
		_uint_16 idx = 1;
		_character_type data;
		/// 从树根开始，循环搜索出这个链是否在此树中存在，直到这条链被搜索完
		while(chain.get_pos_elem(idx++, data) && p_result)
		{
			_uint_16 pos = 0;
			/// 在当前结点的孩子中搜索是否有此数据
			while(p_result && p_result->child_ptr && pos < p_result->child_num)
			{
				if(p_result->child_ptr[pos] && p_result->child_ptr[pos]->data == data)
				{
					/// 下次搜索从这个孩子结点开始搜索
					p_result = p_result->child_ptr[pos];
					break;
				}
				++pos;
			}
			/// 如果在孩子结点中没有找到，那么此树中不存在这条链
			if(!p_result->parent_ptr || pos >= p_result->parent_ptr->child_num)
			{
				return NULL;
			}
		}
	}
	return p_result;
}
///////////////////////////////////////////

///////////////////////////////////////////
/// @brief 导出一个结点所表示的链(返回一个链表, 自行放释放内存)
/// @param node：树中的一个结点
/// @return 成功找到返回链表类型指针，找不到返回NULL
link_list<_character_type>* byte_tree::export_chain(_node_type const *node)
{
	if(node)
	{
		/// 这中方式不好，要改，改成参数传进来，不能这样new，消耗CPU，也容易内存泄露
		_link_list_type *p_link = new _link_list_type;
		/// 头结点不写入链
		while(node->parent_ptr && p_link)
		{
			p_link->insert_front(node->data);
			node = node->parent_ptr;
		}
		/// 如果头结点不是本树的root，说明这个结点不在本树中
		if(this->root != node && p_link)
		{
			delete p_link;
			p_link = NULL;
		}
		return p_link;
	}
	return NULL;
}
///////////////////////////////////////////

///////////////////////////////////////////
/// @brief 从node的孩子结点开始遍历整个树(每个结点进行operate操作)
/// @param operate：函数对象操作基类指针，动态调用指向对象的operator
template<typename _T>
void byte_tree::traver_tree(_node_type* &node, ::op::action<_node_type*, _T> *operate)
{
	_node_type* &ptr = node;
	if(ptr && ptr->child_num > 0)
	{
		_uint_16 pos = 0;
		/// 遍历方式是从左到右，最后根结点
		for(; pos < ptr->child_num; ++pos)
		{
			if(ptr->child_ptr && ptr->child_ptr[pos])
			{
				byte_tree::traver_tree<_T>(ptr->child_ptr[pos], operate);
			}
		}
	}
	if(operate && ptr)
		(*operate)(ptr);		/// 执行操作
}
///////////////////////////////////////////

